package nl.rug.jvleusen.datastructurelib;

import nl.rug.jvleusen.datastructurelib.tree.AVLTree;
import nl.rug.jvleusen.datastructurelib.tree.BinaryTree;
import nl.rug.jvleusen.datastructurelib.tree.NaryTree;

/**
 * This interface is for classes implementing the tree datastructure, this is a
 * datastructure which contains a root node, from this node child nodes cascade
 * down.
 *
 * @author Jeroen van Leusen
 * @see BinaryTree
 * @see AVLTree
 * @see NaryTree
 */
public interface ITree<E, P extends ITree.TreeNode<E>> {

    /**
     * @return Whether this tree doesn't contain any elements.
     */
    public boolean isEmpty();

    /**
     * Returns the height of the tree, this implies how many steps you can take
     * before you would reach the bottom of the tree, will return -1 if the tree
     * is empty.
     *
     * @return Returns the height of the tree, returns -1 if the tree is empty.
     */
    public int height();

    /**
     * @return Returns the rootnode of this tree.
     */
    public P getRoot();

    /**
     * Any implementation of {@link ITree} should be paired with an
     * implementation of {@link TreeNode}
     */
    public interface TreeNode<E> {

        /**
         * @return The data inside this node.
         */
        public E getData();

        /**
         * @return Whether this node has any children.
         */
        public boolean isLeaf();

        /**
         * @return The height spanned by the subtree beneath this node.
         */
        public int height();
    }
}
